# 题目：创建一个基于时间的键值存储类 TimeMap，它支持下面两个操作：

#   1. set(string key, string value, int timestamp)
#       存储键 key、值 value，以及给定的时间戳 timestamp。
#   2. get(string key, int timestamp)
#       返回先前调用 set(key, value, timestamp_prev)所存储的值，其中 timestamp_prev <= timestamp。
#       如果有多个这样的值，则返回对应最大的  timestamp_prev 的那个值。
#       如果没有值，则返回空字符串（""）。
# 时间戳和key唯一确定value

'''
示例：
输入：inputs = ["TimeMap","set","get","get","set","get","get"], inputs = [[],["foo","bar",1],["foo",1],["foo",3],["foo","bar2",4],["foo",4],["foo",5]]
输出：[null,null,"bar","bar",null,"bar2","bar2"]
解释：
TimeMap kv;
kv.set("foo", "bar", 1); // 存储键 "foo" 和值 "bar" 以及时间戳 timestamp = 1
kv.get("foo", 1);  // 输出 "bar"
kv.get("foo", 3); // 输出 "bar" 因为在时间戳 3 和时间戳 2 处没有对应 "foo" 的值，所以唯一的值位于时间戳 1 处（即 "bar"）
kv.set("foo", "bar2", 4);
kv.get("foo", 4); // 输出 "bar2"
kv.get("foo", 5); // 输出 "bar2"
'''


class TimeMap:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.timeDict = {}

    # 字典的使用关键点，访问不在字典里的key，会报错keyError
    #   dict[key]进行访问，key不在dict.keys()里面，会报错keyError
    #   dict.get(key)进行访问，key不在dict.keys()里面，不会报错，会返回None
    #
    #   dict.setdefault(key),key不在dict.keys()里面,等于dict.setdefault(key，None),新增元素
    #   dict.setdefault(key),key在dict.keys()里面,等于访问，等价于dict.get(key)
    #   dict[key] = value,新增元素，或者修改值
    #
    #   总结，字典访问元素的时候容易报错
    def set(self, key: str, value: str, timestamp: int) -> None:
        # key第一次出现，新增元素{timestamp:value}
        if key not in self.timeDict.keys():
            dictTemp = {timestamp: value}
            self.timeDict[key] = dictTemp
        else:
            # key已经在字典里面了，对timeDict[key]，进行新增元素
            self.timeDict[key][timestamp] = value
        return None

    def get(self, key: str, timestamp: int) -> str:

        # Your TimeMap object will be instantiated and called as such:
        # obj = TimeMap()
        # obj.set(key,value,timestamp)
        # param_2 = obj.get(key,timestamp)

        # 查询的key在字典里面，有很多时间戳的值，给的时间戳可能大于已有的，也可能小于已有的,找到比给定时间戳小且最接近的
        if key in self.timeDict.keys():
            # 首先直接查询
            if self.timeDict.get(key).get(timestamp) != None:
                return self.timeDict.get(key).get(timestamp)
            # 查不到再说
            else:
                # key在timeDict[key].keys()其中，但是没有对应时间戳的，需要修改成小的最接近的
                # 查询的时间戳大于已有时间戳就需要先set，再查询
                if timestamp >= min(self.timeDict[key].keys()):
                    # 拿到所有时间戳最近的时间戳，也就是时间戳最大时候的值
                    # 找到离给定时间戳最近，且比给定时间戳小的
                    # int - list不会自动展平
                    interval = [timestamp -
                                i for i in self.timeDict[key].keys()]
                    usefulInterval = [i for i in interval if i > 0]
                    # abs函数不能用于list
                    usefulTime = timestamp - \
                        min([abs(i) for i in usefulInterval])
                    usefulValue = self.timeDict[key][usefulTime]
                    self.set(key, usefulValue, timestamp)
                    return usefulValue
                else:
                    return ''


def inputs(list_1, list_2):
    res = []
    # 不能将其变成字典，因为键值元素不能重复
    #dataDict = dict(zip(list_1, list_2))

    # zip()函数用于将可迭代的对象作为参数，将对象中对应的元素打包成一个个元组，然后返回由这些元组组成的列表。
    # 如果各个迭代器的元素个数不一致，则返回列表长度与最短的对象相同，利用 * 号操作符，可以将元组解压为列表。
    for i, j in zip(list_1, list_2):
        if i == "TimeMap":
            kv = TimeMap()
            res.append('null')
            continue
        elif i == "set":
            kv.set(j[0], j[1], j[2])
            res.append('null')
            continue
        elif i == "get":
            res.append(kv.get(j[0], j[1]))
    return res


if __name__ == "__main__":
    inputs_1 = ["TimeMap", "set", "get", "get", "set", "get", "get"]
    inputs_2 = [[], ["foo", "bar", 1], ["foo", 1], [
        "foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]]
    inputs_3 = ["TimeMap", "set", "set", "get", "get", "get", "get", "get"]
    inputs_4 = [[], ["love", "high", 10], ["love", "low", 20], [
        "love", 5], ["love", 10], ["love", 15], ["love", 20], ["love", 25]]

    print(inputs(inputs_1, inputs_2))
    print(inputs(inputs_3, inputs_4))

#! 注：我手写的代码可以对示例进行良好输出，但是提交的时候运行时间超出限制
'''
写题心得：
        1.一定要好好审题，看清题目是干啥的，最好手动计算一下示例代码，弄清楚运行逻辑，不然会翻来覆去的和输出对不上；（注意注意再注意！！！）
        2.self可以当做对象本身使用，并进行数据的修改；
        3.字典的增加元素、访问元素一定要牢记；
        4.zip函数的好好使用
        5.列表推导式的好好使用，可以大量减少代码撰写
        6.if else语句一定要做好嵌套关系，当不需要返回None时，一定要写else语句进行return
        7.尽量使用三元表达式和lambda表达式
'''
